TNotes.leetcode

Appearance

⏰1040. 移动石子直到连续 II【中等】

1040. 移动石子直到连续 II【中等】 ​

1. 📝 题目描述 ​

在 X 轴上有一些不同位置的石子。给定一个整数数组 stones 表示石子的位置。

如果一个石子在最小或最大的位置，称其为 端点石子。每个回合，你可以将一颗 端点石子 拿起并移动到一个未占用的位置，使得该石子不再是一颗 端点石子。

  • 值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

以长度为 2 的数组形式返回答案，其中：

  • answer[0] 是你可以移动的最小次数
  • answer[1] 是你可以移动的最大次数。

示例 1：

txt
输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

示例 2：

txt
输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

提示：

  • 3 <= stones.length <= 10^4
  • 1 <= stones[i] <= 10^9
  • stones 的值各不相同。

2. 🎯 s.1 - 排序 + 滑动窗口 ​

js
/**
 * @param {number[]} stones
 * @return {number[]}
 */
var numMovesStonesII = function (stones) {
  stones.sort((a, b) => a - b)
  const n = stones.length

  // max moves: choose the larger gap from the two ends
  const maxMoves = Math.max(
    stones[n - 1] - stones[1] - (n - 2),
    stones[n - 2] - stones[0] - (n - 2),
  )

  // min moves: sliding window
  let minMoves = n
  let j = 0
  for (let i = 0; i < n; i++) {
    while (j + 1 < n && stones[j + 1] - stones[i] + 1 <= n) j++
    const already = j - i + 1
    if (already === n - 1 && stones[j] - stones[i] + 1 === n - 1) {
      minMoves = Math.min(minMoves, 2)
    } else {
      minMoves = Math.min(minMoves, n - already)
    }
  }
  return [minMoves, maxMoves]
}
  • 时间复杂度：O(nlog⁡n)，排序的时间复杂度
  • 空间复杂度：O(log⁡n)，排序的栈空间

算法思路：

  • 最大移动次数：从左端或右端开始移动，每次移一格，取两种方案的较大值
  • 最小移动次数：用滑动窗口找一个包含最多石子的连续窗口（大小为 n），缺少的石子数即为移动次数
  • 特殊情况：若窗口内有 n-1 个石子且连续，但最后一个石子不相邻，则需要 2 次移动